//
// Created by Administrator on 2021/5/13.
//

#include <vector>
#include <iostream>
#include <stack>
#include <unordered_map>

using namespace std;

//Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    vector<int> nextLargerNodes(ListNode *head) {
        ListNode *ptr = head;
        unordered_map<ListNode *, int> nextLarger;
        stack<ListNode *> st;
        while (ptr != nullptr) {
            nextLarger[ptr] = 0;
            while (!st.empty() and ptr->val > st.top()->val) {
                nextLarger[st.top()] = ptr->val;
                st.pop();
            }
            st.push(ptr);
            ptr = ptr->next;
        }
        vector<int> ans;
        ptr = head;
        while (ptr != nullptr) {
            ans.push_back(nextLarger[ptr]);
            ptr = ptr->next;
        }
        return ans;
    }
};

class Solution2 {  // 简化
public:
    vector<int> nextLargerNodes(ListNode *head) {
        vector<int> nodeVal;
        stack<int> st;
        while (head != nullptr) {  // 节点值放在数组中
            nodeVal.push_back(head->val);
            head = head->next;
        }
        vector<int> ans(nodeVal.size(), 0);
        for (int i = 0; i < nodeVal.size(); ++i) {
            while (!st.empty() and nodeVal[i] > nodeVal[st.top()]) { // 单调递减栈
                ans[st.top()] = nodeVal[i];
                st.pop();
            }
            st.push(i);
        }
        return ans;
    }
};

int main() {
    ListNode n1{2}, n2{7}, n3{4}, n4{3}, n5{5};
    n1.next = &n2;
    n2.next = &n3;
    n3.next = &n4;
    n4.next = &n5;
    Solution2 sol;
    auto ans = sol.nextLargerNodes(&n1);
    for (const auto &x:ans) cout << x << endl;
    return 0;
}